翻訳と辞書 Words near each other ・ Montgon ・ Montgradail ・ Montgras ・ Montgreenan ・ Montgreenan railway station ・ Montgreleix ・ Montgremay ・ Montgru-Saint-Hilaire ・ Montgrí Castle ・ Montgrí Massif ・ Montgrí, Medes Islands and Baix Ter Natural Park ・ Montguers ・ Montgomery metro station ・ Montgomery metropolitan area ・ Montgomery Middle School ・ Montgomery modular multiplication ・ Montgomery Morrison Cothren ・ Montgomery Motor Speedway ・ Montgomery Motorcycles ・ Montgomery Museum of Fine Arts ・ Montgomery Oliver Koelsch ・ Montgomery P. Berry ・ Montgomery Park ・ Montgomery Park (Portland, Oregon) ・ Montgomery Park Race Track ・ Montgomery Pass, Nevada ・ Montgomery Peak ・ Montgomery Pittman ・ Montgomery Place ・ Montgomery Place, Saskatoon Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Montgomery modular multiplication ： ウィキペディア英語版 Montgomery modular multiplication In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication, introduced in 1985 by the American mathematician Peter L. Montgomery. 〔Peter Montgomery. Modular Multiplication Without Trial Division, ''Math. Computation'', vol. 44, pp. 519–521, 1985.〕 〔Martin Kochanski, (Montgomery Multiplication ) A colloquial explanation.〕 Given two integers ''a'' and ''b'', the classical modular multiplication algorithm computes . Montgomery multiplication works by transforming ''a'' and ''b'' into a special representation known as Montgomery form. For a modulus ''N'', the Montgomery form of ''a'' is defined to be for some constant ''R'' depending only on ''N'' and the underlying computer architecture. If and are the Montgomery forms of ''a'' and ''b'', then their Montgomery product is . Montgomery multiplication is a fast algorithm to compute the Montgomery product. Transforming the result out of Montgomery form yields the classical modular product . Because of the overhead involved in converting ''a'' and ''b'' into Montgomery form, computing a single product by Montgomery multiplication is slower than computing the product in the integers and performing a modular reduction by division or Barrett reduction. However, when many products are required, as in modular exponentiation, the conversion to Montgomery form becomes a negligible fraction of the time of the computation, and performing the computation by Montgomery multiplication is faster than the available alternatives. Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large number, and for these cryptosystems, the increased speed afforded by Montgomery multiplication can be important in practice.〔Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. (Handbook of Applied Cryptography ). CRC Press, 1996. ISBN 0-8493-8523-7, chapter 14.〕 == Modular arithmetic and Montgomery form == Let ''N'' denote a positive integer modulus. The quotient ring Z/''N''Z consists of residue classes modulo ''N'', that is, its elements are sets of the form :$\backslash ,$ where ''a'' ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by ''N'' (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to ''a'' is denoted $\backslash bar\; a$. Equality of residue classes is called congruence and is denoted :$\backslash bar\; a\; \backslash equiv\; \backslash bar\; b\; \backslash pmod.$ Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers ''a'' for which . If ''a'' is an integer, then the representative of $\backslash bar\; a$ is written . When writing congruences, it's common to identify an integer with the residue class it represents. With this convention, the above equality is written $a\; \backslash equiv\; b\; \backslash pmod$. Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if , then the sum of the residue classes $\backslash overline$ and $\backslash overline$ is computed by finding the integer sum , then determining , the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so $\backslash overline\; +\; \backslash overline\; \backslash equiv\; \backslash overline\; \backslash pmod$. If ''a'' and ''b'' are integers in the range , then their sum is in the range and their difference is in the range , so determining the representative in requires at most one subtraction or addition (respectively) of ''N''. However, the product ''ab'' is in the range . Storing the intermediate integer product ''ab'' requires twice as many bits as either ''a'' or ''b'', and efficiently determining the representative in requires division. Mathematically, the integer between 0 and that is congruent to ''ab'' can be expressed by applying the Euclidean division theorem: :$ab\; =\; qN\; +\; r,$ where ''q'' is the quotient $\backslash lfloor\; ab\; /\; N\; \backslash rfloor$ and ''r'', the remainder, is in the interval . The remainder ''r'' is . Determining ''r'' can be done by computing ''q'', then subtracting ''qN'' from ''ab''. For example, the product $\backslash overline\; \backslash cdot\; \backslash overline$ is determined by computing $7\; \backslash cdot\; 15\; =\; 105$, dividing $\backslash lfloor\; 105\; /\; 17\; \backslash rfloor\; =\; 6$, and subtracting $105\; -\; 6\; \backslash cdot\; 17\; =\; 105\; -\; 102\; =\; 3$. Because the computation of ''q'' requires division, it is undesirably expensive on most computer hardware. Montgomery form is a different way of expressing the elements of the ring in which modular products can be computed without expensive divisions. While divisions are still necessary, they can be done with respect to a different divisor ''R''. This divisor can be chosen to be a whole number of machine words, making division and reduction much cheaper. The only mathematical requirement on the auxiliary modulus ''R'' is that it be a positive integer such that . For computational purposes it is also necessary that division and reduction modulo ''R'' be inexpensive, and the modulus is not useful for modular multiplication unless . The Montgomery form or Montgomery representation of the residue class $\backslash bar\; a$ with respect to ''R'' is , that is, it is the representative of the residue class $\backslash overline$. For example, suppose that and that . The Montgomery forms of 3, 5, 7, and 15 are , , , and . Addition and subtraction in Montgomery form are the same as ordinary modular addition and subtraction because of the distributive law: :$aR\; +\; bR\; =\; (a\; +\; b)R,$ :$aR\; -\; bR\; =\; (a\; -\; b)R.$ This is a consequence of the fact that, because , multiplication by ''R'' is an isomorphism on the additive group Z/''N''Z. For example, , which in Montgomery form becomes . Multiplication in Montgomery form, however, is seemingly more complicated. The usual product of ''aR'' and ''bR'' does not represent the product of ''a'' and ''b'' because it has an extra factor of ''R'': :$(aR\; \backslash bmod\; N)(bR\; \backslash bmod\; N)\; \backslash bmod\; N\; =\; (abR)R\; \backslash bmod\; N.$ Computing products in Montgomery form requires removing the extra factor of ''R''. While division by ''R'' is cheap, the intermediate product is not divisible by ''R'' because the modulo operation has destroyed that property. So for instance, the product of the Montgomery forms of 7 and 15 modulo 17 is the product of 3 and 4, which is 12. Since 12 is not divisible by 100, additional effort is required to remove the extra factor of ''R''. Removing the extra factor of ''R'' can be done by multiplying by an integer ''R''′ such that $RR\text{'}\; \backslash equiv\; 1\; \backslash pmod$, that is, by an ''R''′ whose residue class is the modular inverse of ''R'' mod ''N''. Then, working modulo ''N'', :$(aR\; \backslash bmod\; N)(bR\; \backslash bmod\; N)R\text{'}\; \backslash equiv\; (aR)(bR)R^\; \backslash equiv\; (ab)R\; \backslash pmod.$ The integer ''R''′ exists because of the assumption that ''R'' and ''N'' are coprime. It can be constructed using the extended Euclidean algorithm. The extended Euclidean algorithm efficiently determines integers ''R''′ and ''N''′ that satisfy Bézout's identity: , , and: :$RR\text{'}\; -\; NN\text{'}\; =\; 1.$ This shows that it is possible to do multiplication in Montgomery form. A straightforward algorithm to multiply numbers in Montgomery form is therefore to multiply , , and as integers and reduce modulo ''N''. For example, to multiply 7 and 15 modulo 17 in Montgomery form, compute the product of 3 and 4 to get 12 as above. The extended Euclidean algorithm implies that , so . Multiply 12 by 8 to get 96 and reduce modulo 17 to get 11. This is the Montgomery form of 3, as expected. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Montgomery modular multiplication」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.